﻿#include <iostream>

#define MAX(a, b) (a > b ? a : b)

/**
 * 暴力递归方法，以index结尾，最长子数组长度是多少
 */
static int recur(const int* numbers, const size_t numberCount, const int k, const int index)
{
	if (index == 0)
	{
		if (numbers[index] <= k) return 1;
		return 0;
	}

	int sum = 0;
	int finalIndex = index;
	for (int i = index; i >= 0; i--)
	{
		sum += numbers[i];
		if (sum <= k)
			finalIndex = i;
	}

	int prev = recur(numbers, numberCount, k, index - 1);
	int count = index - finalIndex + 1;
	return MAX(prev, count);
}

/**
 * 使用额外的辅助数组
 */
static int byExtraArray(const int* numbers, const size_t numberCount, const int k)
{
	int* minSum = (int*)malloc(numberCount * sizeof(int));
	memset(minSum, 0, numberCount * sizeof(int));
	// 开区间
	int* minSumEnd = (int*)malloc(numberCount * sizeof(int));
	memset(minSumEnd, 0, numberCount * sizeof(int));

	for (int i = numberCount - 1; i >= 0; i--)
	{
		if (i == numberCount - 1)
		{
			minSum[i] = numbers[i];
			minSumEnd[i] = numberCount;
			continue;
		}

		if (minSum[i + 1] >= 0)
		{
			minSum[i] = numbers[i];
			minSumEnd[i] = i + 1;
		}
		else
		{
			minSum[i] = numbers[i] + minSum[i + 1];
			minSumEnd[i] = minSumEnd[i + 1];
		}
	}

	int nextEdge = minSumEnd[0];
	int curIndex;
;	int maxLength = 0;
	int curLength;
	int prevSum = 0;
	int sum;
	for (int left = 0; left < numberCount; left++)
	{
		curIndex = left;
		curLength = 0;
		if (curIndex >= nextEdge)
		{
			nextEdge = minSumEnd[nextEdge];
			prevSum = 0;
		}

		sum = -prevSum;

		while (curIndex < numberCount && sum <= k)
		{
			sum += minSum[curIndex];
			if (sum <= k)
				curLength += minSumEnd[curIndex] - curIndex;

			curIndex = minSumEnd[curIndex];
		}

		maxLength = MAX(maxLength, curLength);
		prevSum += numbers[left];
	}

	free(minSum);
	free(minSumEnd);
	return maxLength;
}

/**
 * 给定一个无序数组arr，其中元素可正，可负，可0，给定一个整数k。求arr所有的子数组中累加和≤k的最长子数组长度。
 * 例如: arr=[3,-2,-4,0,6], k=2, 相加和≤-2的最长子数组为[3,-2,-4,0], 所以结果返回4.
 * 
 * 思路：
 * 声明2个与arr等长的数组:
 * minSum[]: minSum[i] 从i出发的子数组中，最小的累加和
 * minSumEnd[]: minSumEnd[i] 取得最小累加和minSum[i]的时候，右边界在哪个位置
 * 
 * 再利用这2个数组，看从0处出发，即minSum[0]与k作对比，≤k，则将minSumEnd[0]指向的索引的下一个，minSum[j]的那一块，看是否≤k，...
 * 判断完0位置，则看1位置是否在minSumEnd[0]范围内，在的话看minSum[j]的那一块与(minSumEnd[0]-arr[0])是否≤k；不在minSumEnd[0]范围内，则看是否在j的范围内,...
 * 
 */
int main_sumOfTheLongestIntegerSubarrayEqualOrLessThanK()
{
	int numbers[] = {1,-1,1,-1,1,1,1,1,-1,-1};
	int count = sizeof(numbers) / sizeof(int);
	int k = 1;

	int longestSubarrayLength = 0;
	int curSubarrayLength;
	for (int i = 0; i < count; i++)
	{
		curSubarrayLength = recur(numbers, count, k, i);
		longestSubarrayLength = MAX(longestSubarrayLength, curSubarrayLength);
	}

	printf("max length by recur:%d\n", longestSubarrayLength);

	longestSubarrayLength = byExtraArray(numbers, count, k);
	printf("max length by extra array:%d\n", longestSubarrayLength);

	return 0;
}